using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace GeoAzure.Core
{
    /// <summary>
    /// This class is responsible for element insertion in the index.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    internal class Inserter<T> where T : class
    {
        private static readonly IOverflowAlgorithm<T> Overflow = new OverflowAlgorithm<T>();

        internal void Insert(InsertionContext<T> context)
        {
            //var capturedRoot = context.TargetIndex.RootEntry.Node;
            var insertionPath = new Stack<TreeNode<T>>(context.TargetIndex.Level);

            var startingIndexWalk = new IndexWalk<T>(context.TargetIndex.RootEntry);

            BuildInsertionPath(startingIndexWalk, context, insertionPath);
            // not quite sure about this assertion: the depth could change between the time we start walking the index
            // and the time we finish, due to concurrency
            //Debug.Assert(insertionPath.Count == context.TargetIndex.Level, "The insertion path depth does not match the index depth.");

            var targetInsertionNode = insertionPath.Pop();
            // insert the entry
            bool insertionNodeBoundsChanged = targetInsertionNode.AddEntry(context.Entry);
            // check for a split
            TreeNode<T> splitNode = Overflow.HandleNodeOverflow(targetInsertionNode, context);
            if (splitNode != null)
            {
                ExtendParentAfterSplit(targetInsertionNode,
                                       splitNode,
                                       insertionPath, context);
            }
            else
            {
                // did the bounds of the node where we inserted the item actually change?
                // if so, propagate bounds changes to its parent
                if (insertionNodeBoundsChanged)
                {
                    UpdateParent(targetInsertionNode, insertionPath);
                }
                else
                {
                    targetInsertionNode.ReleaseWriteLock();
                }
            }
            //if (capturedRoot != context.TargetIndex.RootEntry.Node)
            //    Debugger.Break();
        }

        private void UpdateParent(TreeNode<T> updatedChildNode, Stack<TreeNode<T>> insertionPath)
        {
            if (insertionPath.Count == 0)    // no parent to update
            {
                updatedChildNode.ReleaseWriteLock();
            }
            else
            {
                // we pop the node that was the parent at the moment we
                // determined the insertion path
                var parentNode = insertionPath.Pop();
                // but the actual parent could have changed, so we must find it
                // by looking at the entries of the initial parent and its
                // right siblings
                var updateChildNodeEntry = FindParentNodeAndEntryForNode(updatedChildNode, ref parentNode);
                // parent-node is write-locked at this stage
                Debug.Assert(updateChildNodeEntry != null);
                bool parentBoundsChanged = parentNode.UpdateEntry(updateChildNodeEntry);
                updatedChildNode.ReleaseWriteLock();

                if (parentBoundsChanged)
                    UpdateParent(parentNode, insertionPath);
                else
                {
                    parentNode.ReleaseWriteLock();
                }
            }
        }

        private static IndexEntry<T> FindParentNodeAndEntryForNode(TreeNode<T> childNode, ref TreeNode<T> parentNode)
        {
            IndexEntry<T> entryForChildNode;
            parentNode.LockForWriting();
            while ((entryForChildNode = parentNode.Entries.Find(e => e.Node == childNode)) == null)
            {
                var parentRightSibling = parentNode.RightSibling;
                Debug.Assert(parentRightSibling != null,
                             "No sibling found in parent node, and no corresponding entry was found so far.");
                parentNode.ReleaseWriteLock();
                parentNode = parentRightSibling;
                parentNode.LockForWriting();
            }
            return entryForChildNode;
        }

        /// <summary>
        /// This method will update the parent level after a node has split. The newly created <see cref="TreeNode{T}"/>
        /// will be inserted in the parent, and the parent bounds will be updated, taking both the <paramref name="originalNode"/>
        /// and the <paramref name="splitNode"/> bounds into account.
        /// </summary>
        /// <param name="originalNode">The node that was split. It is write-locked at this stage.</param>
        /// <param name="splitNode">The node that contains some entries that were originally in <paramref name="originalNode"/>. There are no locks on it at this stage as it is not reachable yet.
        /// </param>
        /// <param name="insertionPath"></param>
        /// <param name="context"></param>
        private void ExtendParentAfterSplit(TreeNode<T> originalNode, TreeNode<T> splitNode, Stack<TreeNode<T>> insertionPath, InsertionContext<T> context)
        {
            var splitEntry = new IndexEntry<T>(splitNode);
            // release the lock as soon as we have an entry for the new node
            // inserting the entry only requires a write lock on the parent
            splitNode.ReleaseReadLock();

            if (insertionPath.Count == 0)   // we reached the top of the index, so we'll have to create a new root
            {
                context.TargetIndex.SplitRootNode(splitEntry);
                originalNode.ReleaseWriteLock();
            }
            else
            {
                var parentNode = insertionPath.Pop();
                var originalNodeEntry = FindParentNodeAndEntryForNode(originalNode, ref parentNode);
                // Note that the parent node is write-locked at this stage

                bool parentNodeBoundsUpdated = parentNode.UpdateEntry(originalNodeEntry);
                // after the next line the sibling (split) node becomes accessible for queries
                // we release the lock after we updated the entry with the new LSN and bounds
                originalNode.ReleaseWriteLock();

                parentNodeBoundsUpdated |= parentNode.AddEntry(splitEntry);

                TreeNode<T> splitParent = Overflow.HandleNodeOverflow(parentNode, context);

                if (splitParent != null)
                {
                    ExtendParentAfterSplit(parentNode, splitParent, insertionPath, context);
                }
                else
                {
                    if (parentNodeBoundsUpdated)
                        UpdateParent(parentNode, insertionPath);
                    else
                    {
                        parentNode.ReleaseWriteLock();
                    }
                }
            }
        }

        /// <summary>
        /// This method will build a stack of <see cref="TreeNode{T}"/> that represents the path to follow
        /// to reach an appropriate <see cref="TreeNode{T}"/> to insert the <see cref="IndexEntry{T}"/>
        /// contained in <paramref name="context"/>
        /// The top of the stack is the <see cref="TreeNode{T}"/> to insert into and it is write-locked.
        /// </summary>
        /// <param name="currentWalk"></param>
        /// <param name="context"></param>
        /// <param name="insertionPath"></param>
        private void BuildInsertionPath(IndexWalk<T> currentWalk, InsertionContext<T> context, Stack<TreeNode<T>> insertionPath)
        {
            var chosenInsertionNodeAtThisLevel = currentWalk.Node;
            bool targetInsertionLevelReached = chosenInsertionNodeAtThisLevel.Level == context.TargetLevel;

            if (targetInsertionLevelReached)
            {
                chosenInsertionNodeAtThisLevel.LockForWriting();
            }
            else
            {
                chosenInsertionNodeAtThisLevel.LockForReading();
            }
            // first check if our start entry is not obsolete
            if (chosenInsertionNodeAtThisLevel.Lsn > currentWalk.ExpectedLsn)
            {
                // if it is then walk the right link chain to build a list of nodes to choose from to replace our start 
                // entry with a good one
                var entriesToChooseFrom = new List<IndexEntry<T>> {new IndexEntry<T>(chosenInsertionNodeAtThisLevel)};

                do
                {
                    chosenInsertionNodeAtThisLevel = chosenInsertionNodeAtThisLevel.RightSibling;
                    if (targetInsertionLevelReached)
                    {
                        chosenInsertionNodeAtThisLevel.LockForWriting();
                    }
                    else
                    {
                        chosenInsertionNodeAtThisLevel.LockForReading();
                    }
                    // TODO: should not have to construct IndexEntry outside of index
                    entriesToChooseFrom.Add(new IndexEntry<T>(chosenInsertionNodeAtThisLevel));
                } while (chosenInsertionNodeAtThisLevel.Lsn != currentWalk.ExpectedLsn);

                chosenInsertionNodeAtThisLevel = ChooseOptimalInsertionEntry(context.Entry, entriesToChooseFrom, chosenInsertionNodeAtThisLevel.Level + 1).Node;
                // now unlock all nodes we did not choose
                for (int i = 0; i < entriesToChooseFrom.Count;i++)
                {
                    var node = entriesToChooseFrom[i].Node;
                    if (node != chosenInsertionNodeAtThisLevel)
                        if (targetInsertionLevelReached)
                            node.ReleaseWriteLock();
                        else
                            node.ReleaseReadLock();
                }
            }

            // OK, we reached the level where we actually want to insert, so we were
            // being passed the target node for insertion
            if (targetInsertionLevelReached)
            {
                insertionPath.Push(chosenInsertionNodeAtThisLevel);
            }
            else
            {
                // our node is read-locked and we have to insert deeper in the tree, so look at its child entries and choose the optimal node
                var chosenOptimalInsertionEntry = ChooseOptimalInsertionEntry(context.Entry, chosenInsertionNodeAtThisLevel.Entries, chosenInsertionNodeAtThisLevel.Level);
                insertionPath.Push(chosenInsertionNodeAtThisLevel);
                var nextWalkEntry = new IndexWalk<T>(chosenOptimalInsertionEntry);
                chosenInsertionNodeAtThisLevel.ReleaseReadLock();
                BuildInsertionPath(nextWalkEntry, context, insertionPath);
            }
        }

        private struct RectangleEnlargement
        {
            internal RectangleEnlargement(IndexEntry<T> entry, double enlargement)
            {
                Entry = entry;
                Enlargement = enlargement;
            }

            public readonly IndexEntry<T> Entry;
            public readonly double Enlargement;
        }

        private class RectangleEnlargementComparer : IComparer<RectangleEnlargement>
        {
            public int Compare(RectangleEnlargement x, RectangleEnlargement y)
            {
                return Math.Sign((sbyte) (x.Enlargement - y.Enlargement));
            }
        }

        private static readonly IComparer<RectangleEnlargement> EnlargementComparer = new RectangleEnlargementComparer();

        private IndexEntry<T> ChooseOptimalInsertionEntry(IndexEntry<T> entryToInsert, List<IndexEntry<T>> entriesToChooseFrom, int currentLevelInIndex)
        {
            // let's first sort the child nodes by increasing order of their area enlargement
            // needed to contain the new element
            GeoRectangle itemBounds = entryToInsert.Bounds;

            if (currentLevelInIndex == 1) // then the children entries are leaves
            {
                var sortedByEnlargement = new RectangleEnlargement[entriesToChooseFrom.Count];
                for (int i = 0; i < entriesToChooseFrom.Count; i++)
                {
                    var bounds = entriesToChooseFrom[i].Bounds;
                    var enlargedBounds = bounds.EnsureContainsRectangle(itemBounds);
                    var enlargement = enlargedBounds.Area - bounds.Area;
                    sortedByEnlargement[i] = new RectangleEnlargement(entriesToChooseFrom[i], enlargement);
                }

                Array.Sort(sortedByEnlargement, EnlargementComparer);

                Debug.Assert(entriesToChooseFrom.Count > 1);
                const int MaxNodesToConsider = 32;
                IndexEntry<T> chosen = null;
                double minOverlapEnlargement = Double.MaxValue;
                for (int i = 0; i < MaxNodesToConsider && i < sortedByEnlargement.Length; i++)
                {
                    var currentBounds = sortedByEnlargement[i].Entry.Bounds;
                    var enlargedBounds = currentBounds.EnsureContainsRectangle(itemBounds);
                    double overlapEnlargement = 0d;
                    for (int j = 0; j < sortedByEnlargement.Length; j++)
                    {
                        if (i == j)
                            continue;
                        var otherNode = sortedByEnlargement[j].Entry;
                        var otherNodeBounds = otherNode.Bounds;
                        var currentOverlapRectangle = currentBounds.IntersectionWith(otherNodeBounds);
                        double currentOverlap = currentOverlapRectangle.HasValue
                                                    ? currentOverlapRectangle.Value.Area
                                                    : 0d;
                        var enlargedOverlapRectangle = enlargedBounds.IntersectionWith(otherNodeBounds);
                        double enlargedOverlap = enlargedOverlapRectangle.HasValue
                                                     ? enlargedOverlapRectangle.Value.Area
                                                     : 0d;

                        overlapEnlargement += (enlargedOverlap - currentOverlap);
                    }
                    if (overlapEnlargement < minOverlapEnlargement)
                    {
                        chosen = sortedByEnlargement[i].Entry;
                        minOverlapEnlargement = overlapEnlargement;
                    }
                    // TODO: resolve ties by choosing rectangle with minimal area enlargement
                }
                return chosen;
            }
            else    // our children are non-leaf nodes
            {
                double minEnlargement = Double.MaxValue;
                IndexEntry<T> chosen = null;

                for (int i = 0; i < entriesToChooseFrom.Count; i++)
                {
                    IndexEntry<T> current = entriesToChooseFrom[i];
                    var bounds = current.Bounds;
                    var enlargedBounds = bounds.EnsureContainsRectangle(itemBounds);
                    var enlargement = enlargedBounds.Area - bounds.Area;
                    if (enlargement < minEnlargement)
                    {
                        minEnlargement = enlargement;
                        chosen = current;
                    }
                }
                return chosen;
            }

        }
    }
}